import java.util.HashMap;

public class NumSubarraysWithSum {

    public int numSubarraysWithSum1(int[] nums, int goal) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0] == goal ? 1 : 0;
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] == 0) {
                dp[i] = nums[i] == goal ? dp[i - 1] + 1 : dp[i - 1];
            } else {
                int temp = 0;
                for (int j = i; j >= 0; j--) {
                    temp += nums[j];
                    if (temp == goal) {
                        dp[i]++;
                    }
                }
            }
            ans += dp[i];
        }
        return ans + dp[0];
    }

    public int numSubarraysWithSum(int[] nums, int goal) {
        HashMap<Integer, Integer> maps = new HashMap<>();
        int sum = 0;
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            maps.put(sum, maps.getOrDefault(sum, 0) + 1);
            sum += nums[i];
            ans += maps.getOrDefault(sum - goal, 0);
        }
        return ans;
    }
}
